package sort;

/**
 * Created with IntelliJ IDEA.
 * Description: 堆排序
 * User: Li_yizYa
 * Date: 2025/9/9
 * Time: 15:08
 */
public class HeapSort {
    private static void heapSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        // 1、创建大根堆
        createHeap(nums);
        // 堆排序
        int end = nums.length - 1;
        while (end > 0) {
            swap(nums, 0, end);
            shiftDown(nums, 0, end);
            end--;
        }
    }
    private static void createHeap(int[] nums) {
        for (int parent = (nums.length - 2) / 2; parent >= 0; parent--) { // 确保从最后一个非叶子结点开始向下调整
            shiftDown(nums, parent, nums.length);
        }
    }
    private static void shiftDown(int[] nums, int parent, int len) {
        int child = parent * 2 + 1; // 通常指向的是当前结点的左孩子
        while (child < len) {
            if (child + 1 < len && nums[child] < nums[child + 1]) { // 确保child指向的是两个节点中最大的那个
                child++;
            }
            if (nums[parent] < nums[child]) {
                swap(nums, parent, child);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }

    }
    private static void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
    public static void main(String[] args) {
        int[] nums = {6,5,4,4,3,1,2,10,8,9,9,9,9};
        heapSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
//    private static void heapSort(int[] nums) {
//        // 1、创建大根堆
//        createHeap(nums);
//        // 2、排序O(nlog2n)
//        int end = nums.length - 1;
//        while (end > 0) {
//            swap(nums, 0, end);
//            shiftDown(nums, 0, end);
//            end--;
//        }
//    }
//    // 创建大根堆
//    private static void createHeap(int[] nums) {
//        for (int parent = (nums.length - 2) / 2; parent >= 0; parent--) { // 确保从最后一个非叶子节点开始
//            shiftDown(nums, parent, nums.length);
//        }
//    }
//    // 向下调整
//    private static void shiftDown(int[] nums, int parent, int len) {
//        int child = (parent * 2) + 1;
//        while (child < len) {
//            if (child + 1 < len && nums[child] < nums[child + 1]) {
//                child++; // 确保child保存的是左右孩子的最大值的下标
//            }
//            if (nums[child] > nums[parent]) {
//                swap(nums, child, parent);
//                parent = child;
//                child = 2 * parent + 1;
//            } else {
//                break;
//            }
//        }
//    }
//    private static void swap(int[] nums, int left, int right) {
//        int tmp = nums[left];
//        nums[left] = nums[right];
//        nums[right] = tmp;
//    }
}
